The present invention generally concerns the field of facsimile transmission of documents, and more particularly concerns an algorithm for compressing facsimile documents based on arithmetic coding.
Arithmetic coding is a well known concept that has been applied in a number of information transmission environments, including facsimile. The basic idea behind arithmetic coding is the mapping of a sequence of symbols to be encoded to a real number in the interval [0.0,1.0), where a square bracket xe2x80x9c[xe2x80x9d indicates that equality is allowed and a curved bracket xe2x80x9c)xe2x80x9d indicates otherwise. The binary expansion of this real number is then transmitted to the arithmetic decoder, where the inverse mapping is performed to retrieve the encoded symbols.
Conventional coding techniques, including Huffman coding, assign distinct code words to different input symbols and achieve data compression by assigning shorter code words to more probable symbols. In arithmetic coding, on the contrary, there is no assignment of specific code words to different input symbols. Instead, the interval [0.0,1.0) is divided into many sub-intervals, each of which is assigned to different input symbols. Less probable symbols get short intervals, and compression is achieved by assigning longer intervals to more probable symbols.
An illustration of this principle is in FIG. 1, which can form the basis of an example of arithmetic coding. The illustration shows that the input symbol takes two possible values, B and W. In a facsimile document, B and W correspond to black and white picture elements (pel) respectively. Let Pb and Pw, be the probabilities of occurrences of B and W respectively. To begin with, the coding interval is [0.0,1.0) with the lower bound L0 0.0 and the upper bound U0=1.0 and the range (which is the difference between the upper and lower bound) R0=1.0. This coding interval is divided into two sub-intervals: [0.0, Pw) corresponding to W, and [Pw 1.0) corresponding to B. The lengths of the sub-intervals are proportional to the probabilities of B and W. If Pb=0.75 and Pw=0.25, then the interval corresponding to B is three times longer than the interval corresponding to W.
When each symbol in the input sequence is coded, the lower bound, the upper bound and the range will experience a change. If the first symbol in the sequence to be encoded is B, the new coding interval is [Pw, 1.0). The upper bound remains the same. The new lower bound is L1=Pw, and the new range is R1=R0 Pb=Pb. The shaded portion in FIG. 1 represents the coding interval.
This coding interval is further sub-divided into two sub-intervals: [Pw, Pw,+PbPw) corresponding to W, and [Pw,+PbPw 1.0) corresponding to B. If the next symbol is a W, the new coding interval is [Pw, Pw,+PbPw). The lower bound remains uncharged at Pw and the new range is R2=R1Pw=PbPw. FIG. 1 shows the changes in the lower bound, the upper bound and the range for the first four symbols, the third and fourth symbols both being B. The lower bound after the third symbol is Pw,+PwPb2 and the coding interval [Pw,+PwPb2, Pw,+PwPb).
In general, if L(nxe2x88x921),R(nxe2x88x921) are the values of the lower bound and the range before the nth symbol is encoded, the following rule is used to change these values:
If the nth symbol is B:
Ln=L(nxe2x88x921),R(nxe2x88x921)Pw
Rn=R(nxe2x88x921)Pb.
If the nth symbol is W:
Ln=L(nxe2x88x921)
xe2x80x83Rn=R(nxe2x88x921)Pw.
The corresponding upper bound Un can be obtained by adding Ln and Rn. Finally, when all the symbols in the input are encoded, the binary expansion corresponding to any real number in the current coding interval is transmitted to the arithmetic decoder. With the knowledge of the probabilities Pb and Pw, the arithmetic decoder follows the same sequence of dividing the intervals to retrieve the coded input.
For example, let the encoder encode only three input symbols and transmit a real number that lies in the coding interval after encoding the first three symbols. The decoder receives this number and lets it be a value, which lies in the interval [Pw,+PwPb2, Pw,+PwPb). To begin decoding, the decoder divides the coding interval [0.0, 1.0) into two intervals: [0.0,Pw) corresponding to W and Pw,1.0) corresponding to B. Since, value lies in the interval corresponding to B, the decoder decodes the first symbol to be B. Now the new coding interval is [Pw,1.0), which in turn is sub-divided into two intervals, [Pw, Pw,+PbPw) corresponding to W and [Pw,+PbPw 1.0) corresponding to B. Since value lies in the interval corresponding to W, the decoder decodes the second symbol to be W and proceeds so on.
An important task in arithmetic coding is the proper estimation of the probabilities Pb and Pw. The compression efficiency that can be achieved depends on the accuracy of these probability estimates. In the discussion presented above, it was implicitly assumed that the values of Pb and Pw, are known and remain the same during the encoding process. In practice, there does not exist a single set of probability values that can efficiently model different facsimile documents. Even within a single document, there is so much variation (for example the borders predominantly contain white pels, whereas the text in the document contains more black pels), it is not conceivable to use a single set of probability values.
A more efficient scheme is to initialize the probabilities to a suitable value at the start of encoding and adapt the values as the encoding proceeds. In the definition of arithmetic coding, there is no restriction that the probabilities remain unchanged during encoding, as long as the decoder can exactly mimic the changes in the probability values. One way of adapting the probabilities is to initialize counts Nb and Nw to 1 and after encoding each input symbol that is either a B or W, the corresponding count is incremented by one. The probabilities of W and B can be obtained from the counts, using,       P    w    =            N      w                      N        w            +              N        b            
and       P    w    =                    N        b                              N          w                +                  N          b                      .  
This initialization is an unbiased initialization, since the initial values for Nb and Nw are equal. It is also possible to use a biased initialization.
The aforementioned method to update the counts Nb and Nw helps to adapt to the local distribution of white and black pels. However, this scheme fails to exploit the redundancy present in the document. The counts Nb and Nw gives a measure of the probability of a pel being white or black. But, the probability of a pel being white or black can be better described if the xe2x80x9ccolorxe2x80x9d of some of the adjacent pels are known. This set of adjacent pels is defined to be the context. In FIG. 2, the pel marked xe2x80x98sxe2x80x99 is being presently encoded and the shaded pels form the context for xe2x80x98sxe2x80x99. The context in this case consists of 4 pels, each of which can be a B or W. So, there are 16 (=24) possible combinations (or states) that the context can assume. The redundancy in the document can be exploited by maintaining a pair of counts for each possible state of the context. When a pel xe2x80x98sxe2x80x99 is encoded, first the state is determined from the context and then the counts corresponding to that state are used in encoding.
It is necessary to exercise caution in selecting the context. Selecting too small a context might not exploit the redundancy in the document well, therefore will decrease the compression efficiency. Selecting too large a context, might just increase the computational complexity and memory requirements without contributing to the compression efficiency. The implementation of arithmetic coding that was used in the simulations for this invention is a modification of the version presented in Witten, I. H., Neal, R. M., Cleary, J. G., xe2x80x9cArithmetic Coding for Data Compressionxe2x80x9d, Communications of the ACM, Volume 30, Number 6, June 1987.
An object of the present invention is the identification of proper contexts for standard facsimile documents, End Of Line (EOL) masking and error detection.
A further object is prevent the effect of a propagation of a transmission error to the whole document by using a combination of one-dimensional and two-dimensional arithmetic coding.
Another object is to present appropriate contexts for the probabilistic models associated with arithmetic coding for one and two dimensional cases.
Yet another object is to provide an error detection scheme to identify the presence of transmission errors.
The present invention is a facsimile system embodying a signal processing method wherein a document is scanned and a sequence of symbols is generated for each of a plurality of scan lines. The sequence of symbols are arithmetic encoded by mapping the symbols to real numbers in a predetermined interval. The real numbers are subject to a binary expansion for transmission by a transmitter. After transmission and reception at a receiver, the received signal is inverse mapped to retrieve the encoded signals.
The present invention further comprises arithmetic coding the scan lines using a combination of one-dimensional and two-dimensional arithmetic coding. Specifically, the arithmetic encoding step further comprises 2-D coding a first plurality of adjacent scan lines, followed by 1-D coding at least one scan line subsequent to the plurality of scan lines. This sequence of 2-D and 1-D coding can be repeated for a plurality of scan lines generated from scanning a document.
Yet another feature of the invention is the application of an end of line (EOL) code to each encoded line. In particular, a first denomination bit is applied whenever a string of N second denomination bits occurs in the compressed bit stream, the combination of N second denomination bits being followed by a first denomination bit to identifying the sequence as not an EOL
A further feature of the invention is to conduct the scanning with a reduced horizontal resolution through minimum difference compression.
Yet another feature of the invention is to apply, at the end of an encoding of a scan line, M bits to represent the xe2x80x9cquarterxe2x80x9d in which the arithmetic coding interval lies.